Сапёр 9x9

Игра Сапёр на поле 9 на 9.

Задача

Как обычно, открыть все ячейки, стараясь не открыть ячейки с минами.

Общее описание

Квадратное поле 9 x 9 (1…9 x 1…9). Количество мин задаётся в начале игры. Что считать координатой X, а что Y, решайте сами, главное, чтобы быть в этом последовательным. Как и в начальных версиях игры под Windows мины расставляются до первого хода. Поэтому подорваться можно уже первым ходом. Всё поле, чтобы не держать в памяти как ПМК, проще рисовать на бумаге. ПМК только выдаёт количество мин вокруг указанной ячейки после каждого хода.

Игровой процесс

Начало

Перед первым запуском несколько констант в регистры. Если используете загрузку образа в эмулятор, то они уже введены.

Регистр Значение
R6 Случайное число. Можно оставить нулевым.
R7 73
R9 0.11828112
Ra 100
Rb 87
Rс 63
Rd 0.35000033

Начало игры: вводим количество мин от 1 до 63. Рекомендую 20. Затем В/О С/П.

ПМК расставит на поле мины случайным образом и по окончании выдаст 3.1415926 (это π).

Игра

Вы задаёте координаты клетки, которую хотите проверить, в виде двузначного числа. От 11 до 99, без нулей!. Как указано выше, сами выбирайте, какой разряд считать координатой по горизонтали, какой по вертикали. И после С/П ПМК отобразит на экране количество мин вокруг указанной ячейки. Если высветится ЕГГ0Г , то это значит, что в указанном месте была мина и вы подорвались – игра закончена.

Окончание

Если вы поняли, где все мины, или подорвались, или просто не нравится текущая расстановка, то начало новой игры как указано выше, только никаких вводов значений в регистры не потребуется. В связи с тем, что генератор случайных чисел постоянно меняет базовое значение, в новой игре будет другая расстановка.

Контроль со стороны ПМК

Программа достаточно медленная, поэтому если используете эмулятор ПМК с ускорением, то включите ускорение. Приятной игры!

Далее только для тех, кто не только играет…

Идеи реализации

В отличие от пользователя, ПМК использует поле не 9 x 9, а 11 x 11. Получаются координаты от 00 до 110, где последняя цифра (для определённости) – это номер по горизонтали.

Лучше показать поле в виде таблицы с числовыми координатами:

100101102103104105106107108109110
90919293949596979899100
8081828384858687888990
7071727374757677787980
6061626364656667686970
5051525354555657585960
4041424344454647484950
3031323334353637383940
2021222324252627282930
1011121314151617181920
0001020304050607080910

В данном случае серая зона по краям – это виртуальные координаты, которые знает ПМК, но не видит пользователь. Обратите внимание, что самый правый ряд – это копия самого левого. При линейном представлении справа от 19 идёт 20, но слева от 21 – тоже 20.

ПМК для распределения мин использует только внутреннее поле, но хранит и в расчётах использует всю таблицу. Это позволяет держать границы поля свободными от мин, что упрощает функции подсчёта.

Что касается обхода, то это лучше увидеть на центральном голубом квадрате. Для примера, пусть пользователь указал координаты 55. В этом случае нужно посчитать мины в ячейках квадрата вокруг него, т. е. в координатах 44, 45, 46, 54, 56, 64, 65, 66.

В общем случае для любой ячейки с координатами P квадрат обхода – это ячейки с координатами P − 11, P − 10, P − 9, P − 1, P + 1, P + 9, P + 10, P + 11. Вот для чего введены виртуальные границы. Чтобы на краях не заниматься сложными расчётами, потому что в виртуальных ячейках всегда нет мин.

Теперь технические детали. У ПМК нет столько регистров памяти, чтобы хранить 111 чисел. Поэтому он для каждой ячейки использует один бит. Для операций с битами используются шестнадцатеричные представления чисел. Т. к. одна шестнадцатеричная цифра может представлять 4 бита, то используя 7 цифр, который максимум в шестнадцатеричных операциях, получаем 7 × 4 = 28. Итого, если использовать 4 регистра памяти, получается 4 × 28 = 112. Как раз хватит для нашего случая.

Второй момент – это вычисление координат обхода. Для удобства формула выше для вычисления ячеек обхода с произвольной координаты P хранится в относительном виде. К начальному P − 11 потом добавляется: +1, +1, +8, +2, +8, +1, +1. А это как раз составляет содержимое загадочной константа из R9 (0.11828112). В ней последняя цифра может быть произвольной не нулевой, потому что используется только как флаг окончания цикла обхода. Но задана явно как два, чтобы использовать эту же константу для косвенного перехода на адрес 12.

Распределение регистров

R0 Рабочий регистр. Используется для циклов.
R1, R2, R4, R8 Битовые поля мин.
R3 Координаты текущей мины.
R5 Счётчик мин.
R6 Случайное число.
R7 73. Адрес процедуры проверки наличия в клетке с координатами из R3 мины.
R9 Константа 0.11828112 для обхода. А хвостик – это адрес начала цикла расстановки мин.
Ra 100. Кроме умножения и вычитания это адрес переход на 00.
Rb 87. Адрес процедуры деление на 4 с остатком
Rc 63. Адрес процедуры проверки координат.
Rd Константа 0.35000033, для вычисления 2x. А хвостик – это адрес начала основного цикла программы.
Re Индекс регистра поля текущей мины.

Текст программы

 # |  00 01 02 03 04 05 06 07 08 09
 00 |  К[x] x→П0 FLg П→xc П→x0 − F√ 0 x→П1 x→П2
 10 |  x→П4 x→П8 П→x6 1 1 × Fπ + К{x} x→П6
 20 |  П→xa × КППc Кx<09 КПП7 Кx=09 x→П3 + КП→xe К∨
 30 |  Кx→Пe FL0 12 Fπ С/П Кx≥0d КППc Кx<0d П→x9 x→П0
 40 |  КПП7 Кx=0a x→П5 1 1 − П→x3 + x→П3 КПП7
 50 |  Fx≠0 53 КП→x5 П→x0 ВП 1 В↑ К{x} x→П0 Fx=0
 60 |  45 П→x5 БП 34 x→П3 КИНВ КИНВ К{x} П→x3 П→xa
 70 |  − × В/О П→x3 КППb x→Пe <-> КППb <-> 1
 80 |  + F10x + КП→xe К∧ К{x} В/О 4 ÷ К[x]
 90 |  FВx К{x} П→xd ÷ Fex К[x] В/О

Объяснение работы программы

Поняв основные идеи, перейдём к программе. В целом программу можно представить так:

Сначала рассмотрим вспомогательные процедуры.

  1. Процедура проверки координат с адреса 63 (Rc). Процедура сохраняет целую часть входного (не отрицательного!) числа в R3 и проверяет, что полученное число состоит из двух ненулевых цифр. В этом случае возвращает отрицательное число. Обращаю внимание, что начинается именно с адреса 63. Дело в том, что число 34, как хвостик команды БП, также код операции К[x]. Выполняются две проверки:
    Число содержитЕсли верноЕсли нет
    Минимум две ненулевых цифрыРезультат > 0Ноль
    Максимум две цифрыРезультат < 0≥ 0
    Результат двух проверок умножается. Если в итоге отрицательное число, то в R3 правильное число из двух ненулевых цифр. Первая проверка использует тот факт, что команда КИНВ первую ненулевую цифру (или единственный ноль) превращает в 8. А в дробной части будут содержаться остальные ненулевые цифры. Команду КИНВ приходится делать дважды, чтобы избежать пустышек на месте дробной части. Вторая проверка просто вычитает из числа 100.
  2. Процедура деление на 4 с остатком с адреса 87 (Rb). Причем остаток сразу используется как показатель функции 2x. Для входного числа X процедура возвращяет пару в регистрах X и Y: 2(X mod 4) и X div 4. Второе число получаем просто – берём целую часть от деления. А первое число получается чуть сложнее. Для этого используем хитрую константу из Rd (0.35000033). Она примерно равна 1 / (4 × Ln(2)), только подобрана так, чтобы после вычисления можно было сразу взять целую часть, а не как для встроенной функции Fxy, которая для 23 даёт 7.9999993, и целая часть не даёт восьмёрку. К тому же Fex вычисляется быстрее, чем Fxy. Получается [e{X / 4} × 4 × Ln(2)], что даёт 2(X mod 4), или числа 1, 2, 4, 8. Хвостик хитрой константы используем как адрес перехода на адрес 33. А обратная величина вместо прямого значения 4 × Ln(2) используется именно для возможности косвенной адресации по хвосту.
  3. Процедура проверки наличия мины в клетке с координатами из R3 с адреса 73 (R7). В результате целое число в диапазоне [0…110] из регистра R3 разбивается на:
    • Re – индекс регистра для определения поля для тестирования;
    • RY – битовая маска (бит) для проверки;
    • RX – результат проверки битовой операции. Не ноль, если есть мина.
    Сначала число проходит процедуру деления №2. Затем результат из множества [1, 2, 4, 8] используется как номер регистра. А целая часть из RY [0…27] снова проходит процедуру деления №2. Целая часть из регистра Y используется для определения разряда бита: 10 в степени [0…6] + 1, а число [1, 2, 4, 8] складывается с числом 10(номер разряда) и получается бит для тестирования, что и делается с помощью операции К∧. Кстати, сам бит остаётся в RY, что позволит его же использовать для последующей установки. Благодаря К{x} возвращается или ноль – нет мин, или не ноль – есть мина. В последнем случае важно, что число меньше единицы. Это пригодится в другом месте.

Теперь можно рассмотреть всю программу.

Адреса 00..06. Ввод числа мин с проверкой. Сохраняется счётчик количества мин в R0 и делается его проверка на ⩾ 1 через FLg, и на ⩽ 63, используя разницу с Rс и затем F√.

Адреса 07..11. Обнуление регистров битовых полей для хранения положения мин.

Адреса 12..19. Генерация случайного числа. Формула последовательности для генерации случайного числа Ni+1 = {Ni × 11 + π}.

Адреса 20..23. Преобразование в координату. Случайное число умножается на 100 и проверяется, что оно состоит их двух ненулевых цифр. Если не так, то возвращается на начало цикла (адрес 12) для генерации другого числа.

Адреса 23..25. Проверка дубликата мины. Если уже есть в этом месте, то снова на начало цикла.

Адреса 26..27. Обнуления текущей координаты, чтобы пользователь не подглядел случайно и удаление этого нуля из стека с помощью операции сложения, чтобы придвинуть битовую маску.

Адреса 28..30. Установка бита для новой мины.

Адреса 31..32. Цикл по числу мин.

Адреса 23..34. Вывод флага окончания инициализации или неудачного выбора координаты для проверки, и остановка для ожидания хода пользователя. Адрес этого фрагмента кода хранится в Rd.

Адреса 35..37. Проверка ввода пользователя. После простой проверки на ≥ 0, что важно для процедуры проверки из Rc, последняя вызывается, с сохранение ввода в R3. Если введена неправильная координата, то переход на начало цикла (Rd).

Адреса 38…42. Подготовка цикла обхода. Константа для обхода из R9 сохраняется в R0. Делается проверка координаты пользователя (R3) процедурой из R7. Если результат удачный (ноль), то этот ноль инициализирует счётчик числа мин вокруг (R5).
Стоит пояснить случай не ноль – нарвались на мину. В этом случае число будет меньше единицы (см. процедуру №3) и произойдёт переход на начало программы (Ra, адрес=00). А там FLg от нуля и выдаст ошибку.

Адреса 43..60. Цикл обхода с подсчётом количества мин. Начинается с −11 (почему обычный минус от нуля справа, а не /-/, будет ясно чуть позже), которое затем прибавляется к координатам выбранной ячейки. Делается проверка через процедуру в R7, и если мина найдена, то промежуточное увеличение счётчика в R5. Затем идёт вычисление прибавки, которое записано в первом разряде регистра R0. После умножения на 10 и сдвига, берётся дробная часть (первый разряд отсекается), сохраняется. И если больше не осталось, то цикл завершается. А если что-то есть, то целое с дробной частью удачно переходит на минус по адресу 45, тем самым оставляя только этот первый разряд, который снова прибавляется к координатам и т. д.

Адреса 61..63. Вывод итога для пользователя. Просто вывод значения счётчика и переход на остановку.

Оставшаяся часть программы уже рассмотрена ранее, когда разбирались подпрограммы.